﻿/**
*@author yuruiqiao
*@date 2020-3-13
*@function of LinkList
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define true 1
#define false 0
//布尔类型
typedef int bool;
//定义表的value类型
typedef int ElemType;
//这边用于表示单链表
typedef struct LNode{
	ElemType data;
	struct LNode * next;
}LNode,* LinkList;

//这边用于表示双链表
typedef struct DNode {
	ElemType data;
	struct DNode* next;
	struct DNode* pred;
	int freq;
}DNode, * DLinkList;

//初始化单链表
LinkList initList() {
	//初始化一个头结点
	LNode* head = (LNode*)malloc(sizeof(LNode));
	head->data = NULL;
	head->next = NULL;
	LinkList linkList = head;
	return linkList;
}

//初始化双链表
DLinkList initDList() {
	DNode* head = (DNode*)malloc(sizeof(DNode));
	head->data = NULL;
	head->next = NULL;
	head->pred = NULL;
	head->freq = 0;
	DLinkList dLinkList = head;
	return dLinkList;
}

//头插入O(1)
bool headInsert(LinkList linkList, ElemType x) {
	if (linkList == NULL)
		return false;
	LNode* head = linkList;
	//head->next==NULL时相当于尾插入
	linkList = head->next;
	LNode* node = (LNode*)malloc(sizeof(LNode));
	node->next = linkList;
	node->data = x;
	head->next = node;
}

//尾插入O(n)
bool EndInsert(LinkList linkList, ElemType x) {
	if (linkList == NULL)
		return false;
	while (linkList->next != NULL)
		linkList = linkList->next;
	linkList->next = (LNode*)malloc(sizeof(LNode));
	linkList->next->data = x;
	linkList->next->next = NULL;
	return true;
}

//生成长度为num的随机单链表O(n)
void RandList(LinkList linkList,int num) {
	if (linkList == NULL)
		return false;
	srand((unsigned)time(NULL));
	for (int i = 0;i <num; i++) {
		int x = rand() % 10;
		headInsert(linkList, x);//头插入时间复杂度O(1)
	}
}

//生成长度为num的随机双链表O(n)
void RandDList(DLinkList dLinkList, int num) {
	if (dLinkList == NULL)
		return false;
	srand((unsigned)time(NULL));
	for (int i = 0;i < num; i++) {
		int x = rand() % 10;
		//头插入时间复杂度O(1)
		DNode* node = (LNode*)malloc(sizeof(LNode));
		node->data = x;
		node->freq = 0;
		node->pred = dLinkList;
		node->next = dLinkList->next;
		if(dLinkList->next!=NULL)
			dLinkList->next->pred = node;
		dLinkList->next = node;
	}
}

//计算单链表都长度(不包括头结点)
int Length(LinkList linkList) {
	int length;
	for (length = 0;linkList != NULL;linkList = linkList->next)
		length++;
	return length-1;
}

//按值查找位置(从1开始,不包括头结点)
int LocateElem(LinkList linkList, ElemType data) {
	int index;
	//如果只有头结点
	if (linkList->next == NULL)
		return -1;
	//从第一个元素开始遍历
	linkList = linkList->next;
	for (index = 1;linkList != NULL;linkList = linkList->next,index++) {
		if (linkList->data == data)
			return index;
	}
	return -1;
}

//按位查找第i个元素(从1开始,不包括头结点)
ElemType GetElem(LinkList linkList, int index) {
	if (index < 1|| linkList == NULL) return;
	//从非头结点开始
	linkList = linkList->next;
	for (int i = 1; linkList != NULL;i++) {
		if (i == index)
			return linkList->data;
		linkList = linkList->next;
	}
	return;
}

//插入操作,i从1开始
bool ListInsert(LinkList linkList, int index, ElemType x) {
	if (index < 1 || linkList==NULL)
		return false;
	//只有头结点都情况,尾插入
	if (linkList->next == NULL) {
		EndInsert(linkList, x);
		return true;
	}
	//有后继结点的情况,linkList此时在头结点
	for (int i = 1;linkList->next != NULL;linkList = linkList->next,i++) {
		if (i == index) {
			LNode* node = (LNode*)malloc(sizeof(LNode));
			node->next = linkList->next;
			node->data = x;
			linkList->next = node;
			return true;
		}
	}
	//插入的序号超出链表长度,则尾插入,linkList此时指向尾结点
	EndInsert(linkList,x);
	return true;
}

//删除操作,删除第i个元素
bool ListDelete(LinkList linkList, int index) {
	if (index < 1 || linkList == NULL)
		return false;
	//用于保存前一个结点
	LNode* preNode = linkList;
	//只能删除后继节点
	linkList = linkList->next;
	for (int i = 1;linkList != NULL;linkList = linkList->next,i++) {
		if (i == index) {
			ElemType value = linkList->data;
			//若linkList->next==NULL,则尾删除
			preNode->next = linkList->next;
			free(linkList);
			return true;
		}
		preNode = linkList;
	}
	//i下标超出链表长度
	return false;
}

//打印全部结点,不包含头结点
void PrintList(LinkList linkList) {
	if (linkList == NULL) {
		printf("NULL\n");
		return;
	}
	//只有头结点
	if (linkList->next == NULL) {
		printf("linkList:()\n");
		return;
	}
	printf("linkList:(");
	for (linkList = linkList->next;linkList->next != NULL;linkList = linkList->next) {
		printf("%d,", linkList->data);
	}
	printf("%d)\n", linkList->data);
}

//打印双链表全部结点,不包含头结点
void PrintDList(DLinkList dLinkList) {
	if (dLinkList == NULL) {
		printf("NULL\n");
		return;
	}
	//只有头结点
	if (dLinkList->next == NULL) {
		printf("doubleList:()\n");
		return;
	}
	printf("doubleList:(");
	for (dLinkList = dLinkList->next;dLinkList->next != NULL;dLinkList = dLinkList->next) {
		printf("%d,", dLinkList->data);
	}
	printf("%d)\n", dLinkList->data);
}

//判空
bool isEmpty(LinkList linkList) {
	//本身为空或者只有头结点
	if (linkList == NULL || linkList->next == NULL)
		return true;
	return false;
}

//销毁单链表,后面的二级指针用于将野指针指向空
void Destroy(LinkList linkList, LinkList* plist) {
	if (linkList == NULL)
		return;
	LNode* head = linkList;
	linkList = head->next;
	//删除头结点后第一个元素
	while (linkList != NULL) {
		head->next = linkList->next;
		free(linkList);
		//指针回到头结点的下一个结点
		linkList = head->next;
	}
	free(head);
	*plist = NULL;
}

//删除所有值为x的结点,非递归算法,含头结点
bool delete_all(LinkList linkList, ElemType x) {
	if (linkList == NULL|| linkList->next==NULL)
		return false;
	LNode* preNode = linkList;
	for (linkList = linkList->next;linkList != NULL;linkList = linkList->next) {
		if (linkList->data == x) {
			preNode->next = linkList->next;
			free(linkList);
			linkList = preNode;
		}
	}
	return true;
}

//删除所有值为x的结点,递归算法,含头结点
bool delete_all_recurrence(LinkList linkList, ElemType x) {
	if (linkList == NULL || linkList->next == NULL)
		return false;
	LNode* preNode = linkList;
	linkList = linkList->next;
	if (linkList->data == x) {
		preNode->next = linkList->next;
		free(linkList);
		linkList = preNode;
	}
	return delete_all_recurrence(linkList, x);
}

//单链表逆置,要求空间复杂度O(1),时间复杂度O(n)
bool reverse(LinkList linkList) {
	if (linkList == NULL || linkList->next == NULL)
		return false;
	LNode* p = NULL;
	LNode* q = linkList->next->next;
	while (q != NULL) {
		linkList->next->next = p;
		p = linkList->next;
		linkList->next = q;
		q = q->next;
	}
	linkList->next->next = p;
	return true;
}

//单链表逆置,递归算法,传入的P为NULL,时间复杂度O(n)
bool reverse_recurrence(LinkList linkList, LNode* p) {
	if (linkList == NULL || linkList->next == NULL)
		return false;
	if (linkList->next->next == NULL) {
		linkList->next->next = p;
		return true;
	}
	LNode* q = linkList->next->next;
	if(q != NULL) {
		linkList->next->next = p;
		p = linkList->next;
		linkList->next = q;
	}
	return reverse_recurrence(linkList, p);
}

//逆序输出每个结点的值,不改变结构
void reversePrint(LinkList linkList) {
	if (linkList->next == NULL)
		return;
	reversePrint(linkList->next);
	printf("%d,", linkList->next->data);
}

//冒泡排序O(n^2)
void sort(LinkList linkList) {
	//结点数少于2则不需要排序
	if (linkList == NULL || linkList->next == NULL|| linkList->next->next == NULL)
		return;
	for (int i = Length(linkList) - 1;i > 0;i--) {
		LNode* max = linkList->next;
		LNode* pre = linkList;
		LNode* front = linkList->next->next;
		while (front != NULL) {
			if (max->data > front->data) {
				pre->next = front;
				max->next = front->next;
				front->next = max;
				pre = front;
				front = max->next;
				continue;
			}
			pre = pre->next;
			max = max->next;
			front = front->next;
		}
	}
}

//超出两个链表的公共结点O(n)
LNode* findCommon(LinkList list1, LinkList list2) {
	int length1 = Length(list1),length2 = Length(list2);
	int distance = length1 - length2;
	//下面两个循环至多执行其中一个,让两个链表长度一样
	for(;distance > 0;distance--)
		list1 = list1->next;
	for(;distance < 0;distance++)
		list2 = list2->next;
	for(;list1->next != NULL;list1 = list1->next, list2 = list2->next)
		if (list1 == list2)
			return list1;
	return NULL;
}

//递增输出单链表各个元素,并释放空间,O(n^2)
void PrintDestroy(LinkList linkList) {
	if (linkList == NULL || linkList->next == NULL)
		return;
	while (linkList->next != NULL) {
		LNode* pre = linkList;
		LNode* min = linkList->next;
		LNode* front = min;
		while (front->next != NULL) {
			if (front->next->data < min->data) {
				min = front->next;
				pre = front;
			}
			front = front->next;
		}
		pre->next = min->next;
		printf("%d,", min->data);
		free(min);
	}
}

//基于频度优先的结点访问调节
DNode* Locate(DLinkList dLinkList, ElemType x) {
	DNode* pre = dLinkList;
	DNode* p = dLinkList->next;
	for(;p != NULL;pre = p,p = p->next) {
		if (p->data == x) {
			p->freq++;
			//pre往回遍历找到适合插入的位置
			for (;pre != dLinkList && p->freq >= pre->freq;pre = pre->pred);
			//这边执行插入操作,插入到pre的后面
			p->pred->next = p->next;
			//若p在最后一个结点则不需要这步
			if(p->next!=NULL)
				p->next->pred = p->pred;
			p->pred = pre;
			p->next = pre->next;
			pre->next->pred = p;
			pre->next = p;
			return p;
		}
	}
	return NULL;
}

//单链表后半元素折叠插空到前半段元素O(n)
void foldInsert(LinkList linkList) {
	int len = Length(linkList);
	int k =len - len / 2;
	LNode* position = linkList->next;
	LNode* pre = linkList;
	//先找到第k个位置
	for (int i = 0;i < k;i++)
		pre = pre->next;
	//这里将单链表的后半段逆置O(n)
	reverse(pre);
	LNode* front = pre->next;
	//position和front相隔k个结点
	while(front != NULL && position!=NULL) {
		//修改结点操作
		pre->next = front->next;
		front->next = position->next;
		position->next = front;
		//position则需要跳两个结点
		position = front->next;
		//front指向pre的前一个结点
		front = pre->next;
	}
}
int main() {
	LinkList list = initList();
	RandList(list, 9);
	PrintList(list);
	foldInsert(list);
	PrintList(list);
	Destroy(list,&list);
	PrintList(list);
}




